package com.lw.leetcode.add.e;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 1703. 得到连续 K 个 1 的最少相邻交换次数
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/29 9:20
 */
public class MinMoves {


    public static void main(String[] args) {
        MinMoves test = new MinMoves();

        // 输入：nums = [1,0,0,1,0,1], k = 2
        //输出：1
        //解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。
        //示例 2：
        //
        //输入：nums = [1,0,0,0,0,0,1,1], k = 3
        //输出：5
        //解释：通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。
        //示例 3：
        //
        //输入：nums = [1,1,0,1], k = 2
        //输出：0
        //
        //来源：力扣（LeetCode）
        //链接：https://leetcode.cn/problems/minimum-adjacent-swaps-for-k-consecutive-ones
        //著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

        // 1
//        int[] arr = {1,0,0,1,0,1};
//        int k = 2;

        // 5
        int[] arr = {1, 0, 0, 0, 0, 0, 1, 1};
        int k = 3;

        // 0
//        int[] arr = {1, 1, 0, 1};
//        int k = 2;

        int i = test.minMoves(arr, k);
        System.out.println(i);
    }

    public int minMoves(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (nums[i] == 1) {
                list.add(i);
            }
        }
        int st = 0;
        int end = k;
        int sum = 0;
        LinkedList<Integer> zeroIndexs = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < k; i++) {
            if (nums[i] == 0) {
                count++;
                sum -= i;
                zeroIndexs.add(i);
            }
        }
        int l = 0;
        int r = k - count;
        for (; r < k; r++) {
            sum += list.get(r);
        }
        int min = sum;
        System.out.println(min);
        int size = list.size();
        while (end < length) {
            if (nums[st] == 1) {
                Integer p = zeroIndexs.peek();
                if (p == null) {
                    return 0;
                }
                if (r < size && l >= 0) {
                    int a = st - list.get(l);
                    int b = list.get(r)  - p - p + st;
                    if (a < b) {
                        sum -= b;
                        r--;
                    } else {
                        sum -= a;
                        l++;
                    }
                } else if (r < size) {
                    int b = list.get(r)  - p - p + st;
                    sum -= b;
                    r--;
                } else if (l >= 0) {
                    int a = st - list.get(l);
                    sum -= a;
                    l++;
                }
            } else {
                zeroIndexs.poll();
                if (r < size && l >= 0) {
                    int a = st - list.get(l);
                    int b = list.get(r) - st;
                    if (a < b) {
                        sum -= b;
                        r--;
                    } else {
                        sum -= a;
                        l++;
                    }
                } else if (r < size) {
                    int b = list.get(r) - st;
                    sum -= b;
                    r--;
                } else if (l >= 0) {
                    int a = st - list.get(l);
                    sum -= a;
                    l++;
                }
            }
            if (nums[end] == 1) {
                Integer p = zeroIndexs.peekLast();
                if (p == null) {
                    return 0;
                }
                if (r + 1 < size && l - 1 >= 0) {
                    int a = p - list.get(l - 1);
                    int b = list.get(r + 1) - p;
                    if (a < b) {
                        sum += a;
                        l--;
                    } else {
                        sum += b;
                        r++;
                    }
                } else if (l - 1 >= 0) {
                    int a =p - list.get(l - 1);
                    sum += a;
                    l--;
                } else if (r + 1 < size) {
                    int b = list.get(r + 1)  - p;
                    sum += b;
                    r++;
                }
            } else {
                zeroIndexs.add(end);
                if (r + 1 < size && l - 1 >= 0) {
                    int a = end - list.get(l - 1);
                    int b = list.get(r + 1) - end;
                    if (a < b) {
                        sum += a;
                        l--;
                    } else {
                        sum += b;
                        r++;
                    }
                } else if (l - 1 >= 0) {
                    int a = end - list.get(l - 1);
                    sum += a;
                    l--;
                } else if (r + 1 < size) {
                    int b = list.get(r + 1) - end;
                    sum += b;
                    r++;
                }
            }
            end++;
            st++;
            System.out.println(sum);
            min = Math.min(min, sum);
        }
        return min;
    }

}
